package com.longge;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-04 01:30
 */
public class Permutation {
    ArrayList<List<Character>> res = new ArrayList<>();

    public String[] permutation(String S) {
        ArrayList<Character> path = new ArrayList<>();
        char[] chars = S.toCharArray();
        backtrack(chars, path);
        return res.stream().map(cs -> {
            StringBuilder sb = new StringBuilder();
            cs.forEach(sb::append);
            return sb.toString();
        }).collect(Collectors.toList()).toArray(new String[]{});
    }

    private void backtrack(char[] chars, ArrayList<Character> path) {
        if (path.size()==chars.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (char aChar : chars) {
            if (path.contains(aChar)) continue;
            path.add(aChar);
            backtrack(chars,path);
            path.remove(path.size()-1);
        }
    }
}
